/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
     {
        if(list1==NULL)  return list2;
        if(list2==NULL)  return list1;

        ListNode*newhead=NULL; ListNode*newtail=NULL;
         while(list1&&list2)
         {
            if(list1->val<list2->val)
            {
                if(newhead==NULL)
                {
                    newhead=list1;
                    newtail=list1;
                }
                else           
                {
                    newtail->next=list1;
                    newtail=newtail->next;
                }
                list1=list1->next;
            }
            else
              {
                if(newhead==NULL)
                {
                    newhead=list2;
                    newtail=list2;
                }
                else
                {
                    newtail->next=list2;
                    newtail=newtail->next;
                }
                list2=list2->next;
              }        
         }
         if(list1==NULL)
         {
            newtail->next=list2;
         }
          if(list2==NULL)
         {
             newtail->next=list1; 
         }
         return newhead;
    }
};
